import string
import time
import sys, threading
import Queue
import socket, struct

# logger

logQueue = Queue.Queue()
logWriterThread = None
def writeLog():
  ''' log writer '''
  while True:
    (outfile, outstr) = logQueue.get(True)
    print >> outfile, outstr

def log(local_time, remote_time, msg): # logger
  ''' logger api. only print none-zero timestamp '''
  global logWriterThread
  if not logWriterThread:
    logWriterThread = threading.Thread(target = writeLog)
    logWriterThread.start()
  if remote_time > 0:
    logQueue.put((sys.stderr, "L %s %d # R %s %d # %s" % (
      time.strftime("%x %X", time.localtime(local_time)), local_time,
      time.strftime("%x %X", time.localtime(remote_time)), remote_time, msg)))
  elif local_time > 0:
    logQueue.put((sys.stderr, "L %s %d # %s" % (
      time.strftime("%x %X", time.localtime(local_time)), local_time, msg)))
  else:
    logQueue.put((sys.stderr, "%s" % (msg)))

# integer <-> binary format

def uint2bin(u):
  ''' convert unsigned int to binary format '''
  return struct.pack('>I', u)

def ulong2bin(ul):
  ''' convert unsigned long long to binary format '''
  return struct.pack('>Q', ul)

def u1282bin(u128):
  ''' convert unsigned int-128 to binary format '''
  return struct.pack('>Q', (u128 >> 64)) + struct.pack(
      '>Q', (u128 & ((1 << 64) - 1)))

def bin2uint(b):
  ''' convert 4-bytes binary to unsigned int '''
  return struct.unpack('>I', b)[0]

def bin2ulong(b):
  ''' convert 4-bytes binary to unsigned int '''
  return struct.unpack('>Q', b)[0]

def bin2u128(b):
  ''' convert 16-bytes binary to unsigned int128 '''
  return ((bin2ulong(b[:8]) << 64) | bin2ulong(b[8:]))

# ip address util

def ip_bin2str(ip_bin):
  '''
    convert 4/16-bytes binary format of ip address to human readable format
  '''
  try:
    if len(ip_bin) == 4:
      return socket.inet_ntop(socket.AF_INET, ip_bin)
    else:
      return socket.inet_ntop(socket.AF_INET6, ip_bin)
  except Exception as e:
    log(0, 0, "ERROR in ip_bin2str: ip_bin=%r. %r" % ip_bin, e)
    return ''

def ip_str2bin(ip_str, is_ipv6):
  ''' convert human readable format ip address to 4/16-bytes binary format '''
  try:
    if not is_ipv6:
      return socket.inet_pton(socket.AF_INET, ip_str)
    else:
      if '.' in ip_str: # ::ffff:a.b.c.d
        return socket.inet_pton(socket.AF_INET, ip_str[7:])
      return socket.inet_pton(socket.AF_INET6, ip_str)
  except Exception as e:
    log(0, 0, "ERROR in ip_str2bin: ip_str=%s, AF=%s, %r" % (
      ip_str, is_ipv6, e))
    return ''

def ip_int2str(ip_int, is_ipv6):
  if is_ipv6:
    ip_bin = u1282bin(ip_int)
  else:
    ip_bin = uint2bin(ip_int)
  return ip_bin2str(ip_bin)

# prefix util

def pfx_str2binrange(pfx_str, is_ipv6):
  '''
    convert human readable ip prefix to binary format NETWORK/BROADCAST range
  '''
  ip_str, psize = pfx_str.split('/')
  psize = int(psize)
  network_bin = ip_str2bin(ip_str, is_ipv6)
  if len(network_bin) == 4:
    network_int = bin2uint(network_bin)
    mask = ((1 << (32 - psize)) - 1)
    broadcast_bin = uint2bin(network_int | mask)
  elif len(network_bin) == 16:
    network_int = bin2u128(network_bin)
    #network_high_int = bin2ulong(network_bin[:8])
    #network_low_int = bin2ulong(network_bin[8:])
    mask = ((1 << (128 - psize)) - 1)
    #broadcast_high_bin = ulong2bin(network_high_int | (mask >> 64))
    #broadcast_low_bin = ulong2bin(network_low_int | (mask & ((1 << 64) - 1)))
    #broadcast_bin = broadcast_high_bin + broadcast_low_bin
    broadcast_bin = u1282bin(network_int | mask)
  else:
    psize = 0 # prefix can not convert
    broadcast_bin = network_bin
  return (network_bin, broadcast_bin, psize)

def get_father_prefixes(network_bin, pfx_length):
  network_bin_arr = bytearray(network_bin)
  mask = (1 << (7 ^ (pfx_length & 7)))
  for psize in xrange(pfx_length-1, 7, -1):
    mask <<= 1
    if mask >= 256:
      mask = 1
    if network_bin_arr[psize/8] & mask:
      network_bin_arr[psize/8] ^= mask
    yield (''.join([chr(c) for c in network_bin_arr]), psize)

# BGP UPDATE Class

class BGPUpdateEntry:
  ''' handle BGP UPDATE prefix '''
  def __init__(self, is_ipv6, pfx_dec, monip_dec, monip_bin,
      monas, homeas, path, path_str, bgptime, localtime, n_pfx, update_id):
    # prefix
    self.is_ipv6 = is_ipv6
    self.dec = pfx_dec
    if is_ipv6 and ('.' in self.dec): # ::ffff:a.b.c.d/e
      self.dec = pfx_dec[7:]
      self.is_ipv6 = False
    self.ipbeg_bin, self.ipend_bin, self.length = pfx_str2binrange(
        pfx_dec, is_ipv6)
    if not is_ipv6:
      self.hole_ipbeg = bin2uint(self.ipbeg_bin)
      self.hole_ipend = bin2uint(self.ipend_bin)
    else:
      self.hole_ipbeg = bin2u128(self.ipbeg_bin)
      self.hole_ipend = bin2u128(self.ipend_bin)
    self.n_pfx = n_pfx
    self.update_id = update_id
    # monitor
    self.monip_dec = monip_dec
    self.monip_bin = monip_bin
    # AS path
    self.monas = monas
    self.homeas = homeas
    self.path = path
    self.path_str = path_str
    # time
    self.bgptime = bgptime
    self.localtime = localtime
    # alarm
    self.alarm_id = -1
    self.liveip = ''
    self.is_live = 1
    self.bad_path = ''
    self.bad_path_re = ''
    self.alarm_type = 0

  def length_is_valid(self):
    if not self.is_ipv6:
      return self.length >= 0 and self.length <= 32
    else:
      return self.length >= 0 and self.length <= 128

#def pfx_str2intrange(pfx_str, AF=''):
#  '''
#    convert human readable ip prefix to big integer range
#    AF: IPV4/IPV6/''
#        if AF == '', check whether ip_str contain a ':'
#  '''
#  ip_str, psize = pfx_str.split('/')
#  psize = int(psize)
#  network_bin = ip_str2bin(ip_str, )
#  if len(network_bin) == 4:
#    network_int = bin2uint(network_bin)
#    mask = ((1 << (32 - psize)) - 1)
#    broadcast_int = (network_int | mask)
#  else:
#    network_high_int = bin2ulong(network_bin[:4])
#    network_low_int = bin2ulong(network_bin[4:])
#    mask = ((1 << (128 - psize)) - 1)
#    broadcast_high_int = (network_high_int | mask)
#    broadcast_low_int = (network_low_int | mask)
#    broadcast_int = ((broadcast_high_int << 64) | broadcast_low_int)
#  return (network_int, broadcast_int)
#
#def pfx_str2binstr(pfx_str, AF=''):
#  '''
#    convert human readable ip prefix to '0'/'1' string format
#    AF: IPV4/IPV6/''
#        if AF == '', check whether ip_str contain a ':'
#  '''
#  ip_str, psize = pfx_str.split('/')
#  psize = int(psize)
#  network_bin = ip_str2bin(ip_str, )
#  pfx_binstr = []
#  for i in xrange(len(network_bin)):
#    if not psize:
#      break
#    for j in xrange(7, -1, -1):
#      if not psize:
#        break
#      if network_bin[i] & (1 << j):
#        pfx_binstr.append('1')
#      else:
#        pfx_binstr.append('0')
#      psize -= 1
#  return ''.join(pfx_binstr)
#
#def dotdec2bin(prefix_dec): # deprecated
#  # split on '.' and '/'
#  j = 0
#  pvi = 0
#  dec = [0, 0, 0, 0, 0]
#  for i in xrange(len(prefix_dec)):
#    if prefix_dec[i] == '.' or prefix_dec[i] == '/':
#      dec[j] = int(prefix_dec[pvi:i])
#      j = j + 1
#      pvi = i + 1
#  dec[4] = int(prefix_dec[pvi:])
#  # dot.decimal to binary
#  prefix_bin = [0 for i in xrange(dec[4])]
#  val = (((dec[0] << 24) + (dec[1] << 16) + (dec[2] << 8) + dec[3]) >> (32 - dec[4]));
#  for i in xrange(dec[4]):
#    if (val & 1) == 1: prefix_bin[i] = '1'
#    else: prefix_bin[i] = '0'
#    val = (val >> 1)
#  prefix_bin.reverse()
#  return ''.join(prefix_bin)
#
#def dotdec2bin_v6(prefix_dec):
#  # split on ':' and '/'
#  # ipv6 address example:   1111:1111::/32   1111::1111/32
#  shex = re.split(':?/?', prefix_dec)
#  psize = int(shex[-1])
#  # hex to dec
#  val = 0
#  for i in xrange(len(shex) - 1):
#    if shex[i] == '':
#      n0 = psize - (len(shex) - 2) * 16
#      if n0 > 0:
#        val <<= n0
#    else:
#      val <<= ((4 - len(shex[i])) * 4)
#      for c in shex[i]:
#        val <<= 4
#        val |= IP_CHR_VALUE[c]
#  # decimal to binary
#  prefix_bin = ['0' for i in xrange(psize)]
#  for i in xrange(psize):
#    if (val & 1) == 1:
#      prefix_bin[i] = '1'
#    val >>= 1
#  prefix_bin.reverse()
#  return ''.join(prefix_bin)
#
#def bin2dotdec(prefix_bin):
#  ip = string.atoi(prefix_bin, 2) << (32 - len(prefix_bin))
#  if len(prefix_bin) > 24:
#    return "%d.%d.%d.%d/%d" % (ip >> 24,
#      (ip & 0x00ff0000) >> 16,
#      (ip & 0x0000ff00) >> 8,
#      (ip & 0x000000ff),
#      len(prefix_bin))
#  elif len(prefix_bin) > 16:
#    return "%d.%d.%d/%d" % (ip >> 24,
#      (ip & 0x00ff0000) >> 16,
#      (ip & 0x0000ff00) >> 8,
#      len(prefix_bin))
#  elif len(prefix_bin) > 8:
#    return "%d.%d/%d" % (ip >> 24,
#      (ip & 0x00ff0000) >> 16,
#      len(prefix_bin))
#  else:
#    return "%d/%d" % (ip >> 24, len(prefix_bin))
#
#def bin2dotdec_v6(prefix_bin):
#  ip = string.atoi(prefix_bin, 2) << (128 - len(prefix_bin))
#  shex = ['' for i in xrange(9)]
#  for i in xrange(8):
#    ipseg = (ip & 0xffff)
#    ip >>= 16
#    if not ipseg:
#      shex[7 - i] = '0'
#    else:
#      for j in xrange(4):
#        if ipseg:
#          shex[7 - i] = IP_VALUE_CHR[ipseg & 0xf] + shex[7 - i]
#        else:
#          break
#        ipseg >>= 4
#  prefix_str = ':'.join(shex[ : (len(prefix_bin)+15)/16])
#  prefix_str = re.sub('(:0)+$', '', prefix_str)
#  return prefix_str + '::/' + str(len(prefix_bin))
#
#def bin2fulldotdec(prefix_bin): # TODO deprecated
#  ip = string.atoi(prefix_bin, 2) << (32 - len(prefix_bin))
#  return "%d.%d.%d.%d/%d" % (ip >> 24,
#    (ip & 0x00ff0000) >> 16,
#    (ip & 0x0000ff00) >> 8,
#    (ip & 0x000000ff),
#    len(prefix_bin))
#
#def bin2fulldotdec_v6(prefix_bin):
#  ip = string.atoi(prefix_bin, 2) << (128 - len(prefix_bin))
#  shex = ['' for i in xrange(8)]
#  for i in xrange(8):
#    ipseg = (ip & 0xffff)
#    ip >>= 16
#    if not ipseg:
#      shex[7 - i] = '0'
#    else:
#      for j in xrange(4):
#        if ipseg:
#          shex[7 - i] = IP_VALUE_CHR[ipseg & 0xf] + shex[7 - i]
#        else:
#          break
#        ipseg >>= 4
#  return ':'.join(shex) + '/' + str(len(prefix_bin))
#
#def bin2range(prefix_bin):
#  ip = string.atoi(prefix_bin, 2) << (32 - len(prefix_bin))
#  if len(prefix_bin) == 32: return (ip, ip)
#  else: return (ip, ip + (1 << (32 - len(prefix_bin))))
#
#def bin2range_v6_upto64(prefix_bin):
#  if len(prefix_bin) > 64:
#    return (0, 0)
#  ip = string.atoi(prefix_bin, 2) << (64 - len(prefix_bin))
#  if len(prefix_bin) == 64:
#    return (ip, ip)
#  else:
#    return (ip, ip + (1 << (64 - len(prefix_bin))))
#
#def dotdec2int(ip_dec):
#  decs = string.split(ip_dec, '.')
#  return ((int(decs[0]) << 24) + (int(decs[1]) << 16) + (int(decs[2]) << 8) + int(decs[3]));
#
#def dotdec2int_v6(ip_dec):
#  # split on ':'
#  # ipv6 address example:   1111:1111::1
#  if ip_dec[-1] == ':':
#    ip_dec = ip_dec[:-1]
#  shex = re.split(':', ip_dec)
#  # hex to dec
#  val = 0
#  for i in xrange(len(shex)):
#    if shex[i] == '':
#      n0 = 128 - (len(shex) - 1) * 16
#      if n0 > 0:
#        val <<= n0
#    else:
#      val <<= ((4 - len(shex[i])) * 4)
#      for c in shex[i]:
#        val <<= 4
#        val |= IP_CHR_VALUE[c]
#  return val
#
#def int2dotdec(ip):
#  return "%d.%d.%d.%d" % (ip >> 24, (ip & 0x00ff0000) >> 16, (ip & 0x0000ff00) >> 8, (ip & 0x000000ff))
#
#def int2dotdec_v6(ip):
#  shex = ['' for i in xrange(8)]
#  for i in xrange(8):
#    ipseg = (ip & 0xffff)
#    ip >>= 16
#    if not ipseg:
#      shex[7 - i] = '0'
#    else:
#      for j in xrange(4):
#        if ipseg:
#          shex[7 - i] = IP_VALUE_CHR[ipseg & 0xf] + shex[7 - i]
#        else:
#          break
#        ipseg >>= 4
#  ip_str = ':' + ':'.join(shex) + ':'
#  ip_str = re.sub(':0(:0)+:', '::', ip_str) # at least two :0:
#  b, e = (0, len(ip_str))
#  if ip_str[1] != ':':
#    b += 1
#  if ip_str[-2] != ':':
#    e -= 1
#  return ip_str[b:e]
#
def asn2int(asn):
  if len(asn) == 0: return 0
  dots = string.split(asn, ".")
  if len(dots) == 1: return int(dots[0])
  if len(dots) == 2: return (int(dots[0]) << 16) + int(dots[1])
  return 0

#def asn2sbin(asn):
#  asn_sbin = []
#  while asn > 0:
#    if (asn & 1) == 1: asn_sbin.append('1')
#    else: asn_sbin.append('0')
#    asn >>= 1
#  asn_sbin.reverse()
#  return ''.join(asn_sbin)

def isPrivateASN(asn):
  return asn >= 64512 and asn <= 65534

def isReservedASN(asn):
  """
    23456:           reserved for 4-bytes ASN trans.
    [56320,  64495]: reserved by IANA
    [64496,  64511]: reserved for documentation RFC-5398
    [64512,  65534]: Designated for private use (Allocated to the IANA)
    65535:           reserved by IANA
    [65536,  65551]: reserved for documentation RFC-5398
    [65552, 131071]: reserved
  """
  return (asn >= 56320 and asn <= 64511) or (
    asn >= 65535 and asn <= 131071) or (asn > 4294967295)

if __name__ == '__main__':
  ips = ['0123:4567:89ab:cdef::', '123:4567:89ab:cdef::1',
      'fedc:ba98:7654:3210::02', '::', '0::', '1::', '2::3', '3:4::', ]
  for i in ips:
    b = ip_str2bin(i, True)
    #print type(b)
    print '%r %s' % (b, i)
    print '%r %s' % (b, ip_bin2str(b))
  prefixes = ['0.0.0.0/0', '1.2.3.4/32', '0123:4567:89ab:cdef::/64', '123:4567:89ab:cdef::/64',
      'fedc:ba98:7654:3210::/67', '::/32', '0::/32', '1::/35', '2::/32', '3:4::/11',
      '::/112', '5::/111', '7:8:a::/64', '::/1', '0:0:1:1:0:0:1::/112']
  for f in prefixes:
    ipbeg_bin, ipend_bin, pfx_length = pfx_str2binrange(f, ':' in f)
    print "%r\n%r %d %s\n" % (ipbeg_bin, ipend_bin, pfx_length, f)
  # father
  f = 'ffff:ffff:ffff:ffff:ffff:ffff:ffff::/112'
  ipbeg_bin, ipend_bin, pfx_length = pfx_str2binrange(f, True)
  print "%r\n%r %d %s\n" % (ipbeg_bin, ipend_bin, pfx_length, f)
  for b, f in get_father_prefixes(ipbeg_bin, pfx_length):
    print "%r %d" % (b, f)
    #print '%d %d' % (bin2u128(ipbeg_bin), bin2u128(ipend_bin))

